The present invention relates to systems for displaying digital images and, more particularly, to systems employing error diffusion halftoning for displaying digital images.
A digital image is typically represented as an array of picture elements or pixels at some point during its storage and processing. The pixels, in turn, are represented by a value that quantifies the intensity of one or more chromatic color components of the image at the spatial coordinates represented by the pixel. The intensity is typically expressed as a value on a scale of gray levels extending between the “gray” extremes of black and white. In the case of a color image, the image is typically decomposed into a plurality of color planes. Each color plane comprises a gray scale image representing the intensity of the pixels for one of the three (for example, red, green, and blue) or four (for example, cyan, magenta, yellow, and black) color components of the image. The color image is created by superimposing the color planes for the image.
To provide visually appealing, realistic images, the intensity of a pixel is commonly expressed with a resolution of as many as eight or twelve bits. With eight bits the intensity can be resolved to 256 levels and with twelve bits the intensity can be resolved to 4096 levels. On the other hand, display mechanisms such as printers, typically cannot display a pixel at such fine levels of resolution. Most printers are limited to binary resolution, that is, the choice between depositing or not depositing a drop of ink at the pixel location. Some printers can select among a limited number of dot sizes or light and dark inks of a component color, but the resolution is still typically much coarser than that afforded by the input value for the pixel. To simulate the color resolution of the image, printers are designed to trade spatial resolution for color resolution in a process known as halftoning. In response to the high resolution input values for pixels of a region of the image, the printer is controlled to deposit ink at some percentage of the pixels in the corresponding region of the printed image. If done correctly, the human visual system will interpret the spaced dots of ink as an area of gray or color approximating the gray or color of the corresponding region of the original image.
One common halftoning method is “ordered dithering.” The printer is instructed to deposit a drop of ink at a location on the print medium if the input value of the pixel at that location exceeds a threshold value. If the pixel's input value is less than the threshold, ink is not deposited at the location. In ordered dithering, a threshold matrix is conceptually overlaid on the output medium and differing thresholds included in the matrix are associated with the various pixel locations on the medium. While ordered dithering is computationally conservative, the probabilistic nature of the process produces unwanted artifacts under many conditions and, for some applications, it is desirable to apply a process than reduces the likelihood of these artifacts.
Error diffusion halftoning is a halftone method intended to improve on the results produced by ordered dithering. For error diffusion halftoning the high resolution input intensity value for the pixel is also compared to a threshold value to determine if ink is to be deposited at a pixel location. However, the threshold, which is often set at approximately one-half the maximum value of the pixel, generally does not vary as a function of pixel location. To achieve the halftone effect, the difference between the input value of a pixel and its “as printed” value or error is distributed among its unprinted neighbors and when a neighbor is printed, the accumulated error is added to the input intensity to obtain augmented input that is compared to the intensity threshold. For example, FIG. 1 schematically illustrates the distribution of error to neighboring pixels 22, 24, 26, and 28 when printing the exemplary pixel 20. For simplicity in the example, it is assumed that the pixel 20 has no accumulated error (Δ=0) and the augmented input value (A) is equal to the input value of the intensity of the pixel (V=239). Since the augmented input intensity (A=239) exceeds the threshold (T=127), the printer is passed an instruction if the form of a binary value (B=1) to deposit ink at the pixel location. The difference between the augmented input value (A) and the “as printed” value of the pixel (B×255=1×255) is the total error (δ=−16) which is distributed among the unprinted neighbors of pixel 20. In the example, the error is distributed according to the error filter weights first proposed by Floyd and Steinberg, ADAPTIVE ALGORITHM FOR SPATIAL GREY SCALE, SID INT. SYM. DIGEST OF TECH. PAPERS, 1975, that is, 7/16 of the total error (−7) is distributed to the pixel 22 immediately to the left of the printed pixel 20. Lesser portions of the error are distributed to three other pixels, 3/16 to pixel 28, 5/16 to pixel 26, and 1/16 to pixel 24 of the row immediately following the row in which the printed pixel 20 is located. Other error diffusion algorithms distribute different portions of the total error to other sets of pixels in the neighborhood of the printed pixel.
FIG. 2 schematically illustrates the accumulation of error for a pixel 40 and the effect of accumulated error on the threshold determination made when the pixel is printed. Images are typically printed in raster scan order and diffused error is accumulated for a pixel 40 as the neighboring pixels 42, 44, and 46 in the preceding row and the pixel 48 immediately to the left of the current pixel 40 are printed. In other known algorithms error is accumulated in a like fashion but in differing proportions and from different pixels in the neighborhood. When it is time to print the current pixel 40, the input value (V=230) is augmented by the accumulated error (Δ=25) to obtain the augmented input value (A=V+Δ=230+25=255) which is compared to the threshold value (T=127). Since the augmented input intensity exceeds the threshold, ink will be deposited at the current pixel 40 but since the augmented value (A) equals the “as printed” value (B×255=1×255) there is no error (δ=0) to distribute to neighboring pixels. Since the “as printed” value of the binary pixel is either the minimum or maximum value of the pixel, substantial positive and negative error can accumulate. The accumulated error may be sufficient cause a pixel to be printed or not printed even though its input intensity value would justify the opposite result.
The magnitude of the threshold for error diffusion halftoning is generally independent of location and error diffusion is generally more accurate than the ordered dithering method. However, like ordered dithering, error diffusion is a quantization process and can produce artifacts in certain areas of an image. Error diffusion halftoning can produce “worms” or patterns of visible lines of dots, particularly in highlight areas. In addition, the diffusion of error to neighboring pixels can delay highlights by producing heavier patterns of dots in the later pixels of a halftone region. In midtone areas, error diffusion can produce a checker board effect that can visually interfere with a smooth transition between regions of the image. Error diffusion can also cause dots of differing colors to be deposited at the same pixel location. A magenta dot on a cyan dot produces a nearly black dot which can give the image a grainy look.
To reduce the artifacts produced by the four pixel diffusion of the Floyd and Steinberg algorithm, error filters with additional weights have been proposed to further diffuse the error. Filters with additional weights require more computation and can accentuate certain artifacts while reducing others. In addition, error diffusion combined with perturbation or dithering has been proposed. However, these methods are computationally expensive and often add the artifacts of dithering to the artifacts produced by error diffusion. A third method of artifact reduction is to perform a spatial examination with the original input pixel values and use the results of the examination to alter an error diffusion halftone threshold to make it easier or harder to deposit ink at the pixel. This method is very computationally intensive because of the need to perform the examination in addition to the halftoning process.
What is desired, therefore, is an improved halftoning method that reduces artifacts produced by the error diffusion halftone method and conserves computational resources.